#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{

	AVLTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}


	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;  //balance factor
};


template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

	//更新平衡因子
	void upbf(Node* root)
	{
		if ((root->_left && root->_right) || (!root->_left && !root->_right))
		{
			root->_bf = 0;
		}
		else
		{
			if ((root->_left != nullptr && root->_right == nullptr))
				root->_bf = -1;
			else
				root->_bf = 1;
		}
	}

	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kv.first < cur->_kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//控制平衡
		while (parent)
		{
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;      
			}
			if (parent->_bf == 0)//已经平衡
			{
				break;
			}
		    else if (parent->_bf == -1 || parent->_bf == 1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//需要旋转调整
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//四种旋转
				//1.右单旋
				if (parent->_bf == -2 && parent->_left->_bf == -1)
				{
					RotateR(parent);
					break;
				}
				//2.左单旋
				else if (parent->_bf == 2 && parent->_right->_bf == 1)
				{
					RotateL(parent);
					break;
				}
				//3.左右双旋
				else if (parent->_bf == -2 && parent->_left->_bf == 1)
				{
					RotateLR(parent);
					break;
				}
				//4.右左双旋
				else if (parent->_bf == 2 && parent->_right->_bf == -1)
				{
					RotateRL(parent);
					break;
				}
				else
				{
					assert(false);
				}
			}
			//平衡树有问题
			else
			{
				assert(false);
			}
		}
		return true;
	}

	//右单旋
	void RotateR(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		if(pparent == nullptr)
		{
			_root = subL;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = subL;
			}
			else
			{
				pparent->_right = subL;
			}
		}

		subL->_parent = pparent;
		subL->_right = parent;
		parent->_parent = subL;
		parent->_left = subLR;
		//如果左子树的右子树存在，改变一下它的父节点指针
		if (subLR)
		{
			subLR->_parent = parent;
		}
		//更新平衡因子
		//subL->_bf = 0;
		//parent->_bf = 0;
		upbf(subL);
		upbf(parent);
		//upbf(subLR);
	}

	//左单旋
	void RotateL(Node* parent)
	{
		Node* pparent = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		if (pparent == nullptr)
		{
			_root = subR;
		}
		else
		{
			if (pparent->_right == parent)
			{
				pparent->_right = subR;
			}
			else
			{
				pparent->_left = subR;
			}
		}
		subR->_parent = pparent;
		subR->_left = parent;
		parent->_parent = subR;
		parent->_right = subRL;
		//如果左子树的右子树存在，改变一下它的父节点指针
		if (subRL)
		{
			subRL->_parent = parent;
		}
		//更新平衡因子
		//subR->_bf = 0;
		//parent->_bf = 0;
		upbf(subR);
		upbf(parent);
		//upbf(subRL);
	}

	//左右双旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_left);
		RotateR(parent);
	}

	//右左双旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

	//中序遍历
	void InOder()
	{
		_InOder(_root);
	}

	void _InOder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOder(root->_right);
	}

	//检查高度
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "Error:" << root->_kv.first << ":" << root->_kv.second << " 因子现在为：" << root->_bf << endl;
			cout << "Error:" << root->_kv.first << ":" << root->_kv.second << " 因子应该为：" << rightHeight - leftHeight << endl;

		}
		return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;
		//对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return (rightHeight - leftHeight) <= 1 ? true : false;
	}
private:
	Node* _root = nullptr;
};


void TestAVLTree()
{

	AVLTree<int, int> t;
	int a[] = { 4,2,6,1,3,5,15,7,16,14,12,21,13,4,8,9,18,10,23,34,33,25,17,0};
	for (auto& e : a)
	{
        t.Insert(make_pair(e, e));
		cout << "Insert:" << (bool)t.IsBalance()<<endl;
	}
	t.InOder();
}